package com.hardy.basic;

import com.hardy.leecode.model.TreeNode;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * Author: Hardy
 * Date:   2021/1/20
 * Description:
 **/
public class Tree {

    // 236.二叉树的最近公共祖先
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) return root;
        TreeNode l = lowestCommonAncestor(root.left, p, q);
        TreeNode r = lowestCommonAncestor(root.right, p, q);
        if (l != null && r != null) return root;
        return l != null ? l : r;
    }

    // 94.二叉树的中序遍历
    public void inorderTraversal(TreeNode root, List<Integer> res) {
        if (root == null) return;
        inorderTraversal(root.left, res);
        res.add(root.val);
        inorderTraversal(root.right, res);
    }

    // 98 验证二叉搜索树
    public boolean isValidBST(TreeNode root, Integer lower, Integer upper) {
        if (root == null) return true;
        if (lower != null && lower >= root.val) return false;
        if (upper != null && upper <= root.val) return false;
        return isValidBST(root.left, lower, root.val) && isValidBST(root.right, root.val, upper);
    }

    // 100. 相同的树
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) return true;
        if (p == null || q == null || p.val != q.val) return false;
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }

    // 104. 二叉树的最大深度
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        int leftHeight = maxDepth(root.left);
        int rightHeight = maxDepth(root.right);
        return Math.max(leftHeight, rightHeight) + 1;
    }

    // 111. 二叉树的最小深度
    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        int h1 = minDepth(root.left);
        int h2 = minDepth(root.right);
        if (h1 == 0 && h2 == 0) return 1;
        if (h1 == 0 || h2 == 0) return Math.max(h1, h2) + 1;
        return Math.min(h1, h2) + 1;
    }

    // 958. 二叉树的完全性检验
    public boolean isCompleteTree(TreeNode root) {
        boolean f = false;
        LinkedList<TreeNode> q = new LinkedList<>();
        q.addLast(root);

        while (!q.isEmpty()) {
            TreeNode node = q.removeFirst();
            if (f && node != null) return false;
            if (node == null) {
                f = true;
                continue;
            }
            q.addLast(node.left);
            q.addLast(node.right);
        }
        return true;
    }

    // 222. 完全二叉树的节点个数
    public int countNodes(TreeNode root) {
        if (root == null) return 0;
        // 二分统计层数
        int lvl = countLevel(root.left);
        int lvr = countLevel(root.right);

        if (lvl == lvr)
            return countNodes(root.right) + (1 << lvl);
        else
            return countNodes(root.left) + (1 << lvr);
    }

    public int countLevel(TreeNode root) {
        int level = 0;
        while (root != null) {
            level++;
            root = root.left;
        }
        return level;
    }

    // 230. 二叉搜索树中第K小的元素
    public int kthSmallest(TreeNode root, int k) {
        return getK(root, new int[]{k});
    }

    private Integer getK(TreeNode node, int[] k) {
        if (node == null) return null;

        Integer v = getK(node.left, k);
        if (v != null) return v;

        k[0] = k[0] - 1;
        if (k[0] == 0) return node.val;

        return getK(node.right, k);
    }

    // 110. 平衡二叉树
    public boolean isBalanced(TreeNode root) {
        return height(root) >= 0;
    }

    public int height(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftHeight = height(root.left);
        if (leftHeight == -1) return -1;

        int rightHeight = height(root.right);
        if (rightHeight == -1 || Math.abs(leftHeight - rightHeight) > 1) {
            return -1;
        } else {
            return Math.max(leftHeight, rightHeight) + 1;
        }
    }

    public TreeNode gen() {
        Integer[] a = {5, 4, 6, 1, 2, 3, 7};

        Queue<TreeNode> q = new LinkedList<>();
        TreeNode root = new TreeNode(a[0]);
        q.offer(root);

        for (int i = 1; !q.isEmpty(); ) {
            TreeNode n = q.poll();

            n.left = a[i] == null ? null : new TreeNode(a[i]);
            if (n.left != null) q.offer(n.left);
            if (++i >= a.length) break;

            n.right = a[i] == null ? null : new TreeNode(a[i]);
            if (n.right != null) q.offer(n.right);
            if (++i >= a.length) break;
        }
        return root;
    }

    public static void main(String[] args) {
        Tree t = new Tree();
        TreeNode node = t.gen();

        //t.inorderTraversal(node, new ArrayList<>());


        //t.isValidBST(node, null, null);
        //System.out.println(t.checkComplete(node));

        //System.out.println(node);

        System.out.println(8);
    }
}
